package com.Offer;

import com.pojo.TreeNode;

/*
    面试题36：二叉搜索树和双向链表
    题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
    要求不能创建任何新的结点，只能调整树中结点指针的指向。
 */
public class demo36 {
    public static void main(String[] args) {

    }

    public static TreeNode Convert(TreeNode pRootOfTree){
        TreeNode lastList = covertNode(pRootOfTree,null);
        TreeNode pHead = lastList;
        while(pHead != null && pHead.left != null){
            pHead = pHead.left;
        }
        return pHead;
    }

    public static TreeNode covertNode(TreeNode root,TreeNode lastList){
        if (root == null){
            return null;
        }
        TreeNode cur = root;
        if(cur.left != null){
            lastList = covertNode(cur.left,lastList);
        }
        cur.left = lastList;
        if(lastList != null){
            lastList.right = cur;
        }
        if(cur.right != null){
            lastList = covertNode(cur.right,lastList);
        }
        return lastList;
    }
}
